Icelandair có nguồn gốc từ hãng Flugfélag Akureyrar, được thành lập ở Akureyri trên bờ phía bắc Iceland, từ năm 1937. Hoạt động bắt đầu từ năm 1938 bằng 1 thủy phi cơ Waco YKS-7. Năm 1940 hãng dời trụ sở về Reykjavík và đổi tên thành Flugfélag Íslands. Vào năm 1944, một hãng hàng không khác tên là Loftleiðir được 3 viên phi công thành lập. Ban đầu 2 hãng Loftleiðir và Flugfélag Íslands tập trung vào các tuyến đường quốc nội.

Năm 1945 Flugfélag Íslands (Iceland Airways Ltd.) mở tuyến bay quốc tế đầu tiên tới Scotland và Đan Mạch. Các tuyến đường quốc tế thường xuyên bắt đầu từ năm 1946 bằng máy bay B-24 Liberator thuê của Scottish Airways. Trong khi đó Loftleiðir bắt đầu mở các tuyến quốc tế từ năm 1947, và dịch vụ giá rẻ xuyên qua Bắc Đại Tây Dương bắt đầu từ năm 1953. Trong thời gian này IATA định giá cho các hãng hàng không bay giữa châu Âu và Bắc Mỹ và mọi hãng hàng không đều phải áp dụng một giá. Loftleiðir lúc đó không là thành viên của IATA và phải tự định giá của mình sao cho có thể cạnh tranh được với các hãng khác, do đó biến hãng thành hãng được ưa chuộng cho các du khách qua lại giữa châu Âu và Bắc Mỹ.

Năm 1973 Flugfélag Íslands và Loftleiðir hợp nhất dưới tên Flugleiðir và tên tiếng Anh là Icelandair. Phần lớn các chuyến bay từ Hoa Kỳ tới châu Âu đều bay qua Iceland khiến cho đảo này trở thành điểm trung chuyển cho các khách du hành từ Hoa Kỳ sang châu Âu và ngược lại.

Sau khi hợp nhất, Icelandair là công ty chủ cho cả hai hãng. Năm 1997, hãng lập thêm hãng phụ Air Iceland, để đảm nhận các tuyến đường quốc nội và các tuyến đường ngắn. Tháng 1/2002, Flugleiðir-Icelandair Group là công ty có 11 công ty con, trong đó Icelandair là lớn nhất. Tháng 3/2005 tập đoàn đổi tên thành "FL Group". Tháng 10/2005, FL Group bán các hãng hàng không cùng các dịch vụ du lịch và tập đoàn mới Icelandair Group được thành lập. Icelandair có 2.565 nhân viên (tháng 3/2007).[2]